package GraphType.eightqueen;

import java.util.Scanner;
/*
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，
即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。
* */
public class DFS_Solution {
    static int N = 10, cnt, n;
    static int a[] = new int[N];//a[i]表示第i行的皇后放于第a[i]列上

    //查看从第row行开始，到第n行结束，皇后可以有多少种放法
    static void dfs(int row) {
        if (row == n + 1) {
            //产生了一组解
            cnt++;
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (check(row, i)) {
                a[row] = i;
                dfs(row + 1);
                a[row] = 0;
            }
        }
    }

    //检测当前x,y坐标下的对角线及同列有没有皇后已放置
    private static boolean check(int x, int y) {
        for (int i = 1; i <= x; i++) {
            if (a[i] == y) return false;//同列存在皇后
            if (a[i] + i == x + y) return false;//正对角线存在皇后
            if (i - a[i] == x - y) return false;//反对角线存在皇后
        }
        return true;
    }

    public static void main(String[] args) {
        n = new Scanner(System.in).nextInt();
        dfs(1);
        System.out.println(cnt);
    }
}
